package demo1;

import java.util.LinkedList;
import java.util.Queue;

//用队列实现栈
//两个队列
//入栈时，把数据放到不空的队列中，
//出栈时，因为此时要出去的元素在队尾
//所以，将不空的队列里的 size-1 个元素移到另一个队列中，留一个就是我们要出栈的元素

class MyStack2 {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;


    public MyStack2() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    //哪个队列不为空，就放到哪个队列里
    //都空的话，放哪都一样
    public void push(int x) {
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    //把不空的队列 出队size - 1 个元素 到另一个队列
    //剩下的一个就是要出栈
    public int pop() {
        if (empty()) {
            return -1;
        }

        Queue<Integer> qu1 = queue1;
        Queue<Integer> qu2 = queue2;

        //如果qu1是空的，交换，保证qu1拿到不空的队列
        if (qu1.isEmpty()) {
            qu1 = queue2;
            qu2 = queue1;
        }

        int size = qu1.size();//记录初始大小
        for (int i = 0; i < size - 1; i++) {
            qu2.offer(qu1.poll());
        }
        return qu1.poll();

    }

    //与出栈基本相同
    public int top() {
        if (empty()) {
            return -1;
        }

        Queue<Integer> qu1 = queue1;
        Queue<Integer> qu2 = queue2;

        //如果qu1是空的，交换，保证qu1拿到不空的队列
        if (qu1.isEmpty()) {
            qu1 = queue2;
            qu2 = queue1;
        }

        int size = qu1.size();//记录初始大小
        for (int i = 0; i < size - 1; i++) {
            qu2.offer(qu1.poll());
        }

        //拿到栈顶元素
        int ret = qu1.peek();
        //再将元素放入qu2
        qu2.offer(qu1.poll());
        return ret;
    }

    public boolean empty() {
        if (queue1.isEmpty() && queue2.isEmpty()) {
            return true;
        }
        return false;
    }
}
